/**
 * 前缀和 会超时
 */
function maxSubArray(nums: number[]): number {
  let max = nums[0]
  let pre = [max]
  for (let i = 1; i < nums.length; i++) {
    pre[i] = pre[i - 1] + nums[i]
    max = Math.max(max, pre[i])
    for (let j = 0; j < i; j++) {
      max = Math.max(max, pre[i] - pre[j])
    }
  }
  return max
}
/**
 * 动态规划
 * 求解整个数组的最大子串和
 * 可以转变成 求前 n-1项 的最大子串和
 * 再结合最后一项进行确定
 */
function maxSubArray2(nums: number[]): number {
  let max = nums[0]
  let dp = 0
  for (let i = 0; i < nums.length; i++) {
    dp = Math.max(dp + nums[i], nums[i])
    max = Math.max(dp, max)
  }
  return max
}
exports.maxSubArray = maxSubArray2